package algorithm.leetcode;

import java.util.Arrays;

/**
 * @author wuwen
 * @since 2023/12/7
 */
public class NO4_寻找两个正序数组的中位数 {
    public static void main(String[] args) {

    }

    static class SolutionPerformance {
        /**
         * 其实可以只用合成一半的数组就够了
         */
        public double findMedianSortedArrays(int[] paramA, int[] paramB) {
            // 只需要前半个数组
            int length = paramA.length + paramB.length;
            int needLength = length / 2 + 1;
            // index为新数组下标，i为A的，j为B的。
            int index = 0, i = 0, j = 0;
            int[] merge = new int[needLength];
            // 进行前半部分数组的合成
            while (index < needLength) {
                int a = i < paramA.length ? paramA[i] : Integer.MIN_VALUE;
                int b = j < paramB.length ? paramB[j] : Integer.MIN_VALUE;
                if (a >= b) {
                    // 取数组a的数据
                    merge[index] = a;
                    i++;
                } else {
                    // 取数组b的数据
                    merge[index] = b;
                    j++;
                }
                index++;
            }
            return length % 2 == 0 ? (merge[needLength - 1] + merge[needLength - 2]) / 2.0 : merge[needLength - 1];
        }
    }

    static class SolutionInefficient {
        public double findMedianSortedArrays(int[] paramA, int[] paramB) {
            int length = paramA.length + paramB.length;
            int halfLength = length / 2;
            int[] merge = new int[length];
            int index = 0;
            while (index < paramA.length) {
                merge[index] = paramA[index];
                index++;
            }
            while ((index - paramA.length) < paramB.length) {
                merge[index] = paramB[index - paramA.length];
                index++;
            }
            Arrays.sort(merge);
            return length % 2 == 0 ? (merge[halfLength] + merge[halfLength + 1]) / 2.0 : merge[halfLength];
        }
    }

}